/**
 * n为括号总数，求其排列组合中合法的括号序列
 * @param {number} n 
 * @returns 
 * 结果为卡特兰数：C[n,2n]/n+1 , C为组合数
 */
var generatePatenthesis = function (n) {
    const result = []
    backTrack(n, result, 0, 0, "")

    // left为当前s的左括号数，right为右括号数，s为括号字符串
    function backTrack(n, result, left, right, s) {
        // 退出条件
        // 括号无效停止条件：到当前位置时，右括号数量大于左括号数量
        if (right > left) {
            return
        }
        // 获得符合要求的括号组合
        if (left === n && right === n) {
            result.push(s)
            return
        }
        
        // 左括号数未到n，可以添加左括号
        if (left < n) {
            backTrack(n, result, left + 1, right, s + "(")
        }
        // 右括号数小于左括号，可以添加右括号
        if (right < left) {
            backTrack(n, result, left, right + 1, s + ")")
        }
    }

    return result
}